0787. K 站中转内最便宜的航班【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - Bellman-Ford

1. 📝 题目描述

• leetcode

有 n 个城市通过一些航班连接。给你一个数组 flights，其中 flights[i] = [fromi, toi, pricei]，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜，并返回该价格。 如果不存在这样的路线，则输出 -1。

---

示例 1：

输入:
n = 4, flights = [
  [0, 1, 100],
  [1, 2, 100],
  [2, 0, 100],
  [1, 3, 600],
  [2, 3, 200]
], src = 0, dst = 3, k = 1
输出: 700
解释: 城市航班图如上
从城市 0 到城市 3 经过最多 1 站的最佳路径用红色标记，费用为 100 + 600 = 700。
请注意，通过城市 [0, 1, 2, 3] 的路径更便宜，但无效，因为它经过了 2 站。

示例 2：

输入:
n = 3, edges = [
  [0, 1, 100],
  [1, 2, 100],
  [0, 2, 500]
], src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如上
从城市 0 到城市 2 经过最多 1 站的最佳路径标记为红色，费用为 100 + 100 = 200。

示例 3：

输入：
n = 3, flights = [
  [0, 1, 100],
  [1, 2, 100],
  [0, 2, 500]
], src = 0, dst = 2, k = 0
输出：500
解释：
城市航班图如上
从城市 0 到城市 2 不经过站点的最佳路径标记为红色，费用为 500。

---

提示：

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• flights[i].length == 3
• 0 <= fromi, toi < n
• fromi != toi
• 1 <= pricei <= 10^4
• 航班没有重复，且不存在自环
• 0 <= src, dst, k < n
• src != dst

2. 🎯 s.1 - Bellman-Ford

c

#include <string.h>
#include <limits.h>

int findCheapestPrice(int n, int** flights, int flightsSize, int* flightsColSize, int src, int dst, int k) {
    int* dp = (int*)malloc(sizeof(int) * n);
    int* tmp = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) dp[i] = INT_MAX;
    dp[src] = 0;
    for (int i = 0; i <= k; i++) {
        memcpy(tmp, dp, sizeof(int) * n);
        for (int j = 0; j < flightsSize; j++) {
            int u = flights[j][0], v = flights[j][1], w = flights[j][2];
            if (dp[u] != INT_MAX && dp[u] + w < tmp[v]) tmp[v] = dp[u] + w;
        }
        memcpy(dp, tmp, sizeof(int) * n);
    }
    int res = dp[dst];
    free(dp); free(tmp);
    return res == INT_MAX ? -1 : res;
}

js

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
var findCheapestPrice = function (n, flights, src, dst, k) {
  let dp = new Array(n).fill(Infinity)
  dp[src] = 0
  for (let i = 0; i <= k; i++) {
    const tmp = dp.slice()
    for (const [u, v, w] of flights) {
      if (dp[u] !== Infinity) {
        tmp[v] = Math.min(tmp[v], dp[u] + w)
      }
    }
    dp = tmp
  }
  return dp[dst] === Infinity ? -1 : dp[dst]
}

py

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        dp = [float('inf')] * n
        dp[src] = 0
        for _ in range(k + 1):
            tmp = dp[:]
            for u, v, w in flights:
                if dp[u] != float('inf'):
                    tmp[v] = min(tmp[v], dp[u] + w)
            dp = tmp
        return -1 if dp[dst] == float('inf') else dp[dst]

• 时间复杂度：$O(k\times m)$，其中 m 是航班数量
• 空间复杂度：$O(n)$

算法思路：

• 限制最多 k 次中转即最多经过 k+1 条边，进行 k+1 轮 Bellman-Ford 松弛
• 每轮使用上一轮的副本更新，避免在同一轮中多次松弛